
{\magtwo 9. Implementations}

{\magonebf 9.1 List of data structures}

This section lists the data structures for dictionaries, dictionary
arrays, priority queues, and geometric data types currently contained in LEDA. 
For each of the data structures its name and type, the list of LEDA data types 
it can implement, and a literature reference are given.
Before using a data structures $xyz$ the corresponding header file
\<LEDA/impl/$xyz$.h\> has to be included (cf.~section~1.2 for an example).

{\bf 9.1.1 Dictionaries}
\+\cleartabs \hskip 2.7truecm & \hskip 4.5truecm & \hskip 6truecm &\cr
\+$ab\_tree$    &a-b tree           &dictionary, d\_array, {\bf sortseq}&[BC72]\cr
\+$avl\_tree$   &AVL tree           &dictionary, d\_array          &[AVL62]\cr
\+$bb\_tree$    &BB[$\alpha$] tree  &dictionary, d\_array, sortseq &[BM80] \cr
\+$ch\_hashing$ &hashing with chaining &dictionary, d\_array       &[M84]\cr
\+$dp\_hashing$ &dyn. perf. hashing &{\bf h\_array}           &[DKMMRT88,W92]\cr
\+$pers\_tree$  &persistent   tree  &{\bf p\_dictionary}      &[DSST89]\cr
\+$rb\_tree$    &red-black tree     &dictionary, d\_array, sortseq &[GS78] \cr
\+$rs\_tree$    &rand. search tree  &{\bf dictionary}, {\bf d\_array}, sortseq &[AS89]\cr
\+$skiplist$    &skip lists         &dictionary, d\_array, sortseq  &[Pu90]\cr


{\bf 9.1.2 Priority Queues}
\medskip
\+$f\_heap$    &Fibonnacci heap   &{\bf priority\_queue} &[FT87]\cr
\+$p\_heap$    &pairing heap      &priority\_queue       &[SV87]\cr
\+$k\_heap$    &k-nary heap       &priority\_queue       &[M84]\cr
\+$m\_heap$    &monotonic heap    &priority\_queue       &[M84]\cr
\+$eb\_tree$   &Emde-Boas tree    &priority\_queue       &[EKZ77,W92]\cr

{\bf 9.1.3 Geometry}
\medskip
\+$range\_tree$ &range tree     &{\bf d2\_dictionary}, {\bf point\_set}&[Wi85,Lu78]\cr
\+$seg\_tree$   &segment tree         &{\bf seg\_set}      &[B79,Ed82]\cr
\+$ps\_tree$    &priority search tree &\ \ ---             &[MC81]\cr
\+$iv\_tree$    &interval tree        &{\bf interval\_set} &[MC80,Ed82]\cr
\+$delaunay\_tree$ &delaunay tree     &{\bf point\_set}    &[De92]\cr

\vfill\eject

\bigskip
{\magonebf 9.2 User Implementations}

In addition to the data structures listed in the previous section user-defined 
data structures can also be used as actual implementation parameters provided 
they fulfill certain requirements.

\bigskip
{\bf 9.2.1 Dictionaries}
\smallskip
Any class $dic\_impl$ that provides the following operations can be used as 
actual implementation parameter for the $\_dictionary\<K,I,dic\_impl\>$ 
and the $\_d\_array\<I,E,dic\_impl\>$ data types (cf.~sections~4.3 and 4.4).

\begingroup
\parskip 0pt\baselineskip 0pt
\tt {\tt\obeyspaces\gdef {\hskip.5em}} \def\par{\leavevmode\endgraf} \catcode`\`=\active
\obeylines \ttverbatim

typedef ... dic_impl_item;

class dic_impl {

 virtual int  cmp(GenPtr, GenPtr) const = 0;
 virtual int  int_type()          const = 0;
 virtual void clear_key(GenPtr&)  const = 0;
 virtual void clear_inf(GenPtr&)  const = 0;
 virtual void copy_key(GenPtr&)   const = 0;
 virtual void copy_inf(GenPtr&)   const = 0;

public:

 dic_impl();
 dic_impl(const dic_impl&);
 virtual ~dic_impl();

 dic_impl& operator=(const dic_impl&);

 GenPtr key(dic_impl_item)  const;
 GenPtr inf(dic_impl_item)  const;

 dic_impl_item insert(GenPtr,GenPtr);
 dic_impl_item lookup(GenPtr)  const;
 dic_impl_item first_item()    const;
 dic_impl_item next_item(dic_impl_item) const;

 dic_impl_item item(void* p) const { return dic_impl_item(p); }

 void    change_inf(dic_impl_item,GenPtr);
 void    del_item(dic_impl_item);
 void    del(GenPtr);
 void    clear();

 int     size() const;
};

\endgroup


\bigskip
{\bf 9.2.2 Priority Queues}
\smallskip
Any class $prio\_impl$ that provides the following operations can be used as 
actual implementation parameter for the $\_priority\_queue\<K,I,prio\_impl\>$
data type (cf.~section~4.1).

\begingroup
\parskip 0pt\baselineskip 0pt
\tt {\tt\obeyspaces\gdef {\hskip.5em}} \def\par{\leavevmode\endgraf} \catcode`\`=\active
\obeylines \ttverbatim

typedef ... prio_impl_item;

class prio_impl { 

 virtual int  cmp(GenPtr, GenPtr) const = 0;
 virtual int  int_type()          const = 0;
 virtual void clear_key(GenPtr&)  const = 0;
 virtual void clear_inf(GenPtr&)  const = 0;
 virtual void copy_key(GenPtr&)   const = 0;
 virtual void copy_inf(GenPtr&)   const = 0;

public:

 prio_impl();
 prio_impl(int);
 prio_impl(int,int);
 prio_impl(const prio_impl&);
 virtual ~prio_impl();

 prio_impl& operator=(const prio_impl&);

 prio_impl_item insert(GenPtr,GenPtr);
 prio_impl_item find_min() const;
 prio_impl_item first_item() const;
 prio_impl_item next_item(prio_impl_item) const;

 prio_impl_item item(void* p) const { return prio_impl_item(p); }
 
 GenPtr key(prio_impl_item) const;
 GenPtr inf(prio_impl_item) const;

 void del_min();
 void del_item(prio_impl_item);
 void decrease_key(prio_impl_item,GenPtr);
 void change_inf(prio_impl_item,GenPtr);
 void clear();
  
 int  size()  const;
};
\endgroup

\bigskip
{\bf 9.2.3 Sorted Sequences}
\smallskip
Any class $seq\_impl$ that provides the following operations can be used as 
actual implementation parameter for the $\_sortseq\<K,I,seq\_impl\>$ data
type (cf.~section~4.6).

\begingroup
\parskip 0pt\baselineskip 0pt
\tt {\tt\obeyspaces\gdef {\hskip.5em}} \def\par{\leavevmode\endgraf} \catcode`\`=\active
\obeylines \ttverbatim

typedef ... seq_impl_item;

class seq_impl  {

 virtual int  cmp(GenPtr, GenPtr) const = 0;
 virtual int  int_type()          const = 0;
 virtual void clear_key(GenPtr&)  const = 0;
 virtual void clear_inf(GenPtr&)  const = 0;
 virtual void copy_key(GenPtr&)   const = 0;
 virtual void copy_inf(GenPtr&)   const = 0;

public:

 seq_impl();
 seq_impl(const seq_impl&);
 virtual ~seq_impl();

 seq_impl& operator=(const seq_impl&);
 seq_impl& conc(seq_impl&);
 
 seq_impl_item insert(GenPtr,GenPtr);
 seq_impl_item insert_at_item(seq_impl_item,GenPtr,GenPtr);
 seq_impl_item lookup(GenPtr)      const;
 seq_impl_item locate(GenPtr)      const;
 seq_impl_item locate_pred(GenPtr) const;
 seq_impl_item succ(seq_impl_item) const;
 seq_impl_item pred(seq_impl_item) const;
 seq_impl_item item(void* p) const { return seq_impl_item(p); }
 
 GenPtr key(seq_impl_item) const;
 GenPtr inf(seq_impl_item) const;
 
 void del(GenPtr); 
 void del_item(seq_impl_item); 
 void change_inf(seq_impl_item,GenPtr);
 void split_at_item(seq_impl_item,seq_impl&,seq_impl&);
 void reverse_items(seq_impl_item,seq_impl_item); 
 void clear();
 
 int  size()  const;
};

\endgroup

\vfill\eject

\vglue 10cm
\vfill\eject
